package com.example.programmerinterview;

import com.example.structure.ListNode;
import com.example.structure.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 面试题 04.03. 特定深度节点链表
 * 给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
 * <p>
 * 示例：
 * <p>
 * 输入：[1,2,3,4,5,null,7,8]
 * <p>
 * 1
 * /  \
 * 2    3
 * / \    \
 * 4   5    7
 * /
 * 8
 * <p>
 * 输出：[[1],[2,3],[4,5,7],[8]]
 * <p>
 * 思路：层序遍历变种，完全自主作答！！
 */
public class ListOfDepth {
    public ListNode[] listOfDepth(TreeNode tree) {
        if (tree == null) return new ListNode[]{};
        List<ListNode> list = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(tree);
        while (queue.size() > 0) {
            int n = queue.size();
            ListNode listnode = null, dummy = null;
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                if (listnode == null) {
                    listnode = new ListNode(node.val);
                    dummy = listnode;
                } else {
                    listnode.next = new ListNode(node.val);
                    listnode = listnode.next;
                }
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            list.add(dummy);
        }
        ListNode[] res = new ListNode[list.size()];
        return list.toArray(res);
    }
}


